GATE PYQ

GATE IT 2008

Q1.
Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generated by the control unit. While designing the horizontal microprogrammed control unit, single address field format is used for branch control logic. What is the minimum size of the control word and control address register?

Q2.
C program is given below: #include < stdio.h > int main () { int i, j; char a [2] [3] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}}; char b [3] [2]; char p = b; for (i = 0; i < 2; i++) { for (j = 0; j < 3; j++) { (p + 2j + i) = a [i] [j]; } } } What should be the contents of the array b at the end of the program?

Q3.
Consider the C program given below. What does it print? #include < stdio.h > int main () { int i, j; int a [8] = {1, 2, 3, 4, 5, 6, 7, 8}; for(i = 0; i < 3; i++) { a[i] = a[i] + 1; i++; } i--; for (j = 7; j > 4; j--) { int i = j/2; a[i] = a[i] - 1; } printf ("%d, %d", i, a[i]);

Q4.
What is the output printed by the following C code? #include < stdio.h > int main () { char a [6] = "world"; int i, j; for (i = 0, j = 5; i < j; a [i++] = a [j--]); printf ("%s\n", a); }

Q5.
How many distinct BSTs can be constructed with 3 distinct keys?

Q6.
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 IV. 550,149,507,395,463,402,270 Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

Q7.
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 IV. 550,149,507,395,463,402,270 Which of the following statements is TRUE?

Q8.
Which of the following is TRUE?

Q9.
Arrange the following functions in increasing asymptotic order: a. n^{1/3} b. e^n c. n^{7/4} d. n \log^9n e. 1.0000001^n

Q10.
Consider a computer with a 4-ways set-associative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. While accessing the memory location 0C795H by the CPU, the contents of the TAG field of the corresponding cache line is: